package com.algorithm.ch2.lzr.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 无重复字符的最长子串是 "abc"，其长度为 3。
 *
 * @author lzr
 * @date 2018/11/15
 */
public class LengthOfLongestSubstring {

    public static void main(String[] args) {
        int length = lengthOfLongestSubstring2("abcabcbb");
        System.out.println(length);
    }


    /**
     * 第一版
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        int max = 0;
        int change = 0;
        List<Character> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            char m = chars[i];
            if (!list.contains(m)) {
                list.add(m);
                sb.append(m);
                change++;
            } else {
                max = max > change ? max : change;
                list = new ArrayList<>();
                list.add(m);
                String[] split = sb.toString().split(String.valueOf(m));
                if (split.length == 2) {
                    sb = new StringBuilder(split[1]);
                    for (char n : split[1].toCharArray()) {
                        list.add(n);
                    }
                } else {
                    sb = new StringBuilder();
                }
                sb.append(m);
                change = sb.length();
            }
        }
        max = max > change ? max : change;
        return max;
    }


    /**
     * 使用位图法
     * 重新分析，这道题的核心是两个指针的移动，一个快，一个慢
     * 慢指针的移动规则是：当出现字符重复时，
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        int rs = 0;
        // ASCII表共能表示256个字符
        int[] temp = new int[256];
        int left = 0;
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            // 位置
            int val = i + 1;
            if (temp[c] == 0 || temp[c] < left) {
                // 未出现重复
                int change = val - left;
                rs = rs > change ? rs : change;
            } else {
                // 遇到重复，左边指针位置 = 重复字符前一次出现的位置
                left = temp[c];
            }
            // 更新字符出现的位置
            temp[c] = val;
        }
        return rs;
    }

    /**
     * 基于位图法调整
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring3(String s) {
        int rs = 0;
        Map<Character, Integer> map = new HashMap<>();
        Integer left = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            Integer temp = map.get(c) == null ? 0 : map.get(c);
            // 位置
            int val = i + 1;
            if (Integer.valueOf(0).equals(temp) || left.compareTo(temp) > 0) {
                // 未出现重复
                int change = val - left;
                rs = rs > change ? rs : change;
            } else {
                // 遇到重复，左边指针位置 = 重复字符前一次出现的位置
                left = temp;
            }
            // 更新字符出现的位置
            map.put(c, val);
        }
        return rs;
    }
}
